Fixed-point iteration

In numerical analysis, fixed-point iteration is a method of computing fixed points of iterated functions.

More specifically, given a function $f$ defined on the real numbers with real values and given a point $x_0$ in the domain of $f$ , the fixed point iteration is

$x_{n%2B1}=f(x_n), \, n=0, 1, 2, \dots$

which gives rise to the sequence $x_0, x_1, x_2, \dots$ which is hoped to converge to a point $x$ . If $f$ is continuous, then one can prove that the obtained $x$ is a fixed point of $f$ , i.e.,

$f(x)=x$ .

More generally, the function $f$ can be defined on any metric space with values in that same space.

1 Examples
2 Applications
3 Properties
4 References
5 See also
6 External links

Examples

A first simple and useful example is the Babylonian method for computing the square root of a>0, which consists in taking $f(x)=\frac 12\left(\frac ax %2B x\right)$ , i.e. the mean value of x and a/x, to approach the limit $x = \sqrt a$ (from whatever starting point $x_0 \gg 0$ ). This is a special case of Newton's method quoted below.

The fixed-point iteration $x_{n%2B1}=\cos x_n\,$ converges to the unique fixed point of the function $f(x)=\cos x\,$ for any starting point $x_0.$ This example does satisfy the hypotheses of the Banach fixed point theorem. Hence, the error after n steps satisfies $|x_n-x_0| \leq { q^n \over 1-q } | x_1 - x_0 | = C q^n$ (where we can take $q = 0.85$ , if we start from $x_0=1$ .) When the error is less than a multiple of $q^n$ for some constant q, we say that we have linear convergence. The Banach fixed-point theorem allows one to obtain fixed-point iterations with linear convergence.

The fixed-point iteration $x_{n%2B1}=2x_n\,$ will diverge unless $x_0=0$ . We say that the fixed point of $f(x)=2x\,$ is repelling.

The requirement that f is continuous is important, as the following example shows. The iteration

$x_{n%2B1} = \begin{cases} \frac{x_n}{2}, & x_n \ne 0\\ 1, & x_n=0 \end{cases}$

converges to 0 for all values of $x_0$ . However, 0 is not a fixed point of the function

$f(x) = \begin{cases} \frac{x}{2}, & x \ne 0\\ 1, & x = 0 \end{cases}$

as this function is not continuous at $x=0$ , and in fact has no fixed points.

Applications

Newton's method for a given differentiable function $f(x)$ is $x_{n%2B1}=x_n-\frac{f(x_n)}{f'(x_n)}$ . If we write $g(x)=x-\frac{f(x)}{f'(x)}$ we may rewrite the Newton iteration as the fixed point iteration $x_{n%2B1}=g(x_n)$ . If this iteration converges to a fixed point $x$ of $g$ then $x=g(x)=x-\frac{f(x)}{f'(x)}$ so $\frac{f(x)}{f'(x)}=0$ . The inverse of anything is nonzero, therefore $f(x)=0$ : x is a root of f. Under the assumptions of the Banach fixed point theorem, the Newton iteration, framed as the fixed point method, demonstrates linear convergence. However, a more detailed analysis shows quadratic convergence, i.e., $|x_n-x|<Cq^{n^2}$ , under certain circumstances.

Halley's method is similar to Newton's method but, when it works correctly, its error is $|x_n-x|<Cq^{n^3}$ (cubic convergence). In general, it is possible to design methods that converge with speed $Cq^{n^k}$ for any $k\in \Bbb N$ . As a general rule, the higher the $k$ , the less stable it is, and the more computationally expensive it gets. For these reasons, higher order methods are typically not used.

Runge-Kutta methods and numerical Ordinary Differential Equation solvers in general can be viewed as fixed point iterations. Indeed, the core idea when analyzing the A-stability of ODE solvers is to start with the special case $y'=ay$ , where a is a complex number, and to check whether the ODE solver converges to the fixed point $y=0$ whenever the real part of a is negative.^[1]

The Picard–Lindelöf theorem, which shows that ordinary differential equations have solutions, is essentially an application of the Banach fixed point theorem to a special sequence of functions which forms a fixed point iteration.

The goal seeking function in Excel can be used to find solutions to the Colebrook equation to an accuracy of 15 significant figures.^[2]

Some of the "successive approximation" schemes used in dynamic programming to solve Bellman's functional equation are based on fixed point iterations in the space of the return function.^[3]^[4]

Properties

If a function $f$ defined on the real line with real values is Lipschitz continuous with Lipschitz constant $L<1$ , then this function has precisely one fixed point, and the fixed-point iteration converges towards that fixed point for any initial guess $x_0.$ This theorem can be generalized to any metric space.

The speed of convergence of the iteration sequence can be increased by using a convergence acceleration method such as Aitken's delta-squared process. The application of Aitken's method to fixed-point iteration is known as Steffensen's method, and it can be shown that Steffensen's method yields a rate of convergence that is at least quadratic.

References

^ One may also consider certain iterations A-stable if the iterates stay bounded for a long time, which is beyond the scope of this article.
^ M A Kumar (2010), Solve Implicit Equations (Colebrook) Within Worksheet, Createspace, ISBN 1-452-81619-0
^ Bellman, R. (1957). Dynamic programming, Princeton University Press.
^ Sniedovich, M. (2010). Dynamic Programming: Foundations and Principles, Taylor & Francis.

Burden, Richard L.; Faires, J. Douglas (1985). "2.2 Fixed-Point Iteration". Numerical Analysis (3rd ed.). PWS Publishers. ISBN 0-87150-857-5. .

External links

Fixed-point iteration online calculator